Relational database systems are a type of database or database management system that stores information in tables—rows and columns of data. Typically, the rows of a table represent records (collections of information about separate items) and the columns represent fields (particular attributes of a record). An example of a relational database system is the SQL (Structured Query Language) Server database system manufactured and sold by Microsoft Corporation.
Database programs utilize queries to perform searches on one or more databases. Queries are composed of operators that perform a function involving one or more tables. One particular type of query that is frequently used in relational database systems groups records according to the value of one or more columns in the records. A query of this type is often referred to as an aggregation operation, an aggregation query or, simply, an aggregation (“GROUP BY” in SQL). As an example, suppose a business administrator wants to compute a sales total for a set of customers from a number of invoices. Each record represents one invoice and contains, among other things, a customer number and a dollar amount. The administrator might formulate an aggregation query that groups the invoices according to customer number and sums the dollar amounts on the invoices for each customer.
Other operators can be utilized together with an aggregation to perform a more sophisticated query on one or more tables. One such operator is a join operation, also referred to as a join query or a join. A join operation takes information in one table and combines that information with related information in another table. In the example given above, suppose the administrator would also like to see the name of the customer and the phone number of a customer contact (person) for each customer together with the total sales information for the customer. Suppose, also, that the customer name and customer contact information are not listed in the sales table that contains the sales figures—they are listed in a customer table, which contains, among other things, the customer name and contact information for the customer.
In this case, a join operation is first performed to combine the customer name and contact information with the invoice information. Subsequently, the aggregation operation calculates the total sales per customer as outlined above, and the administrator has a result that shows the customer name, the phone number of the customer contact person, and the total sales for that customer. There is, however, a significant cost to performing the join followed by the aggregation, due to the time necessary to perform certain input/output (I/O) operations.
The data records of a database are commonly stored on disk arrays or other forms of non-volatile memory. Queries performed on relational databases, such as the aggregation query, require that all data records be loaded into volatile memory (i.e., random access memory, or “RAM”) for processing. However, relational databases often contain a large amount of data, which surpasses the volatile memory resources. As a result, records are loaded into volatile memory in batches to create a “record store,” and large intermediate results must frequently be written to non-volatile memory such as a disk. Transferring large amounts of data between volatile and non-volatile memory significantly increases the cost of processing a query.
This cost problem is compounded in the case of the query having a join followed by an aggregation. Consider the situation if the sales table contains one million invoices and there are ten thousand different customer records in the customer table. It is doubtful that there is sufficient RAM to load both tables completely into RAM and perform the join in RAM. Therefore, joining the customer table with the sales table requires loading a record from the sales table, identifying the customer number in that record, searching the customer table to locate a record for that customer, loading the record for that customer into RAM, and creating a new record combining the sales and customer information. This requires the computer to access the disk for each record in the sales database, or one million times. The join algorithm outlined above is known as a (simple) nested-loop join algorithm. It is relatively inefficient but it is used here to outline the basic idea of join processing. There are other more efficient join algorithms (hash join, merge join, etc.) but they are considerably more complex and will not be discussed in detail herein. Those skilled in the art will be familiar with the intricacies of these algorithms.
The bulk of the processing overhead in the query described above is related to the join operation. This is clear, since the join operation requires accessing the disk for each record. In this example, the disk is accessed one million times. The time required for a disk access operation is significantly large in comparison to other computer operations. Therefore, the join operation and the disk accesses required therein are prime targets for any endeavor to reduce processing overhead.
If the records used for input to the join operation are reduced, then the overhead of the join operation is also reduced. One way in which the input records to a join operation can be reduced is to perform an additional aggregation—a “pre-aggregation”—prior to computing the join. Continuing on the example query, the total sales per customer could be computed first by processing only the sales table, then joining the resulting table with the customer table.
While this reduces the input to the join, significant overhead is still required for the pre-aggregation. This is because a pre-aggregation operation is held to the same standard as any aggregation operation. That is, the pre-aggregation operation performs a complete aggregation, producing just a single output record for each customer.